//
// Created by wenyaxi on 24-11-1.
//
#include <common.h>

class Solution {
public:
    void reorderList(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return;
        }
        deque<ListNode *> q;
        while (head) {
            q.push_back(head);
            head = head->next;
        }
        auto *dummy = new ListNode(0);
        ListNode *cur = dummy;
        int index = 0;
        while (q.size()>=2) {
            if (index == 0) {
                ListNode *p = q.front();
                q.pop_front();
                cur->next = p;
                cur = p;
                index = 1;
            } else {
                ListNode *p = q.back();
                q.pop_back();
                cur->next = p;
                cur = p;
                index = 0;
            }
        }
        ListNode *p = q.front();
        q.pop_front();
        p->next=nullptr;
        cur->next = p;
    }
};

int main(int argc, char *argv[]) {
    Solution s;
    auto list_node = ListNode::of({
        1, 2, 3, 4, 5
    });
    s.reorderList(list_node);
    return 0;
}
